package main

import "fmt"

//这道题主要是构造前缀树节点的数据结构，帮助解答问题。
//原题
//实现一个 Trie (前缀树)，包含?insert,?search, 和?startsWith?这三个操作。
//
//示例:
//Trie trie = new Trie();
//trie.insert("apple");
//trie.search("apple");   // 返回 true
//trie.search("app");     // 返回 false
//trie.startsWith("app"); // 返回 true
//trie.insert("app");
//trie.search("app");     // 返回 true
//解题
//前缀树的意义
//我们用前缀树这种数据结构，主要是用在在字符串数据集中搜索单词的场景，但针对这种场景，我们也可以使用平衡树和哈希表，而且哈希表可以在O(1)时间内寻找到键值。那为什么还要前缀树呢？
//
//原因有3：
//前缀树可以找到具有同意前缀的全部键值。
//前缀树可以按词典枚举字符串的数据集。
//前缀树在存储多个具有相同前缀的键时可以使用较少的空间，只需要O(m)的时间复杂度，其中 m 为键长。在平衡树中查找键值却需要O(m log n)，其中 n 是插入的键的数量；而哈希表随着大小的增加，会出现大量的冲突，时间复杂度可能增加到O(n)。
//构造前缀树的节点结构

type(
	TrieTree struct {
		bEnd bool
		node [26]*TrieTree
	}
)

func (this *TrieTree) insert(val string){
	node := this
	for _, c := range val{
		if node.node[c - 'a'] == nil{
			node.node[c - 'a'] = &TrieTree{}
		}
		node = node.node[c - 'a']
	}
	node.bEnd = true
}

func (this *TrieTree) search(val string) bool{
	node := this
	for _, c := range val{
		if node.node[c - 'a'] == nil{
			return false
		}
		node = node.node[c - 'a']
	}
	return node.bEnd
}

func (this *TrieTree) startsWith(val string) bool{
	node := this
	for _, c := range val{
		if node.node[c - 'a'] == nil{
			return false
		}
		node = node.node[c - 'a']
	}
	return true
}

func main(){
	trie := &TrieTree{};
	trie.insert("apple")
	fmt.Println(trie.search("apple"))   // 返回 true
	fmt.Println(trie.search("app"))     // 返回 false
	fmt.Println(trie.startsWith("app")) // 返回 true
	trie.insert("appr")
	fmt.Println(trie.search("app"))    // 返回 true
}

